Data communications and storage systems typically detect transmission or storage errors in blocks of data (“messages”) by checksums over the message bits. A common class of checksums is the linear block code. Linear block codes include, for example, Cyclic Redundancy Check (CRC), Reed-Solomon codes, and Bose, Chaudhuri, and Hocquengham (BCH) codes.
As data communications and storage systems transmit and receive transmitted messages at a faster rate, computation of checksums need to match this rate. In order to accelerate the processing of linear block codes, some techniques attempted to process messages bits in parallel. Many of these techniques still suffered the drawback of requiring a large amount of time because of the large number of message bits they handle and the size of the resulting expressions.
A 32-bit parallel computation of a CRC-32, for example, requires approximately 900 exclusive-OR gates. Some of the expressions handled by past techniques also include up to 33 terms. Logic limitations such as gate fan-in and the number of inputs in a field programmable gate array (FPGA) lookup table, required multi-level implementation and a large amount of interconnection wiring. This resulted in limiting the speed of the circuit. In addition, many of these techniques also require large amounts of hardware to handle fluctuations in the rate in which message bits arrived. This translated to additional costs and additional space requirement for the hardware on the system, which was undesirable.
Thus, what is needed is an efficient and cost effective technique for computing linear block codes.